package algorithms;

/**
 * 完全不理解这个算法
 */
public class KMP字符串匹配 {

    public static void main(String[] args) {
        kmpMatcher("ababab", "ab");
    }

    private static void kmpMatcher(String t, String p) {
        int n = t.length();
        int m = p.length();
        int[] pi = computePrefixFunction(p);
        int q = 0;
        for (int i = 1; i <= n; i++) {
            while (q > 0 && p.charAt(q + 1 - 1) != t.charAt(i - 1)) {
                q = pi[q];
            }
            if (p.charAt(q + 1 - 1) == t.charAt(i - 1)) {
                q = q + 1;
            }
            if (q == m) {
                System.out.println("Pattern occurs with shift:" + (i - m));
                q = pi[q];
            }
        }
    }

    /**
     * 假设pattern是ababa：
     * a
     * a
     * <p>
     * ab
     * ab
     * <p>
     * aba
     * aba
     * <p>
     * abab
     * abab
     * <p>
     * ababa
     * ababa
     * =>
     * ababa
     * ..ababa
     * <p>
     * 分解为求解为上面几个子部分的最长真前缀
     *
     * @param p
     * @return
     */
    private static int[] computePrefixFunction(String p) {
        int m = p.length();
        int[] pi = new int[m + 1];
        pi[1] = 0;
        int k = 0;
        for (int q = 2; q <= m; q++) {
            while (k > 0 && p.charAt(k + 1 - 1) != p.charAt(q - 1)) {
                k = pi[k];
            }
            if (p.charAt(k + 1 - 1) == p.charAt(q - 1)) {
                k = k + 1;
            }
            pi[q] = k;
        }
        return pi;
    }
}
